<html>
 <head>
  <meta charset="UTF-8">
 </head>
 <body>
  <h3 data-lake-id="afd1845b" id="afd1845b"><span data-lake-id="u9ccf48a5" id="u9ccf48a5">HashMap 的数据结构</span></h3>
  <p data-lake-id="u42e53f95" id="u42e53f95"><br></p>
  <p data-lake-id="ub99da57f" id="ub99da57f"><span data-lake-id="uac1a45fa" id="uac1a45fa">在Java中，保存数据有两种比较简单的数据结构：数组和链表。</span></p>
  <p data-lake-id="u912038f6" id="u912038f6"><strong><span data-lake-id="u8029d38c" id="u8029d38c">​</span></strong><br></p>
  <p data-lake-id="uf45fb9e2" id="uf45fb9e2"><strong><span data-lake-id="u3c5d0d42" id="u3c5d0d42">数组的特点是：寻址容易，插入和删除困难；而链表的特点是：寻址困难，插入和删除容易。</span></strong></p>
  <p data-lake-id="uc171ca36" id="uc171ca36"><span data-lake-id="ufa7b9353" id="ufa7b9353">​</span><br></p>
  <p data-lake-id="ue2632c7f" id="ue2632c7f"><strong><span data-lake-id="ud6a08bbc" id="ud6a08bbc">常用的哈希函数的冲突解决办法中有一种方法叫做链地址法，其实就是将数组和链表组合在一起，发挥了两者的优势，我们可以将其理解为链表的数组。在JDK 1.8之前，HashMap就是通过这种结构来存储数据的。</span></strong></p>
  <p data-lake-id="u7e65bc5f" id="u7e65bc5f"><img src="https://cdn.nlark.com/yuque/0/2023/png/5378072/1692799464985-6ab71813-5adf-4a17-b273-b6db8c4040e8.png?x-oss-process=image%2Fwatermark%2Ctype_d3F5LW1pY3JvaGVp%2Csize_25%2Ctext_SmF2YSA4IEd1IFA%3D%2Ccolor_FFFFFF%2Cshadow_50%2Ct_80%2Cg_se%2Cx_10%2Cy_10"></p>
  <p data-lake-id="u788f96d1" id="u788f96d1"><br></p>
  <p data-lake-id="u3fa03482" id="u3fa03482"><span data-lake-id="u52f3bfa9" id="u52f3bfa9">我们可以从上图看到，左边很明显是个数组，数组的每个成员是一个链表。该数据结构所容纳的所有元素均包含一个指针，用于元素间的链接。我们根据元素的自身特征把元素分配到不同的链表中去，反过来我们也正是通过这些特征找到正确的链表，再从链表中找出正确的元素。其中，根据元素特征计算元素数组下标的方法就是哈希算法，即本文的主角hash()函数（当然，还包括indexOf()函数）。</span></p>
  <p data-lake-id="u18515f95" id="u18515f95"><span data-lake-id="uca5267bb" id="uca5267bb">​</span><br></p>
  <p data-lake-id="u81239075" id="u81239075"><span data-lake-id="ue4931033" id="ue4931033">在JDK 1.8中为了解决因hash冲突导致某个链表长度过长，影响put和get的效率，引入了红黑树。</span></p>
  <p data-lake-id="ua95c2011" id="ua95c2011"><span data-lake-id="u80b39df3" id="u80b39df3">​</span><br></p>
 </body>
</html>